DROPS

Document

Online scheduling of splittable tasks

Authors: Leah Epstein and Rob van Stee

Published in: Dagstuhl Seminar Proceedings, Volume 5031, Algorithms for Optimization with Incomplete Information (2005)

Abstract

We consider online scheduling of splittable tasks on parallel machines. In our model, each task can be split into a limited number of parts, that can then be scheduled independently. We consider both the case where the machines are identical and the case where some subset of the machines have a (fixed) higher speed than the others. We design a class of algorithms which allows us to give tight bounds for a large class of cases where tasks may be split into relatively many parts. For identical machines we also improve upon the natural greedy algorithm in other classes of cases.

Cite as

Leah Epstein and Rob van Stee. Online scheduling of splittable tasks. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{epstein_et_al:DagSemProc.05031.21,
  author =	{Epstein, Leah and Stee, Rob van},
  title =	{{Online scheduling of splittable tasks}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.21},
  URN =		{urn:nbn:de:0030-drops-743},
  doi =		{10.4230/DagSemProc.05031.21},
  annote =	{Keywords: online scheduling , splittable tasks , parallel machines , greedy algorithm}
}

Search Results

Documents authored by Stee, Rob van

Online scheduling of splittable tasks

Abstract

Cite as

Thanks for your feedback!

Could not send message